package com.algorithm.backtrack;

/**
 * Created by mu on 2018/2/6.
 */
public class EightQueue {
    private int arr[][]=new int [8][8];
    private int left[]=new int [15];
    private int right[]=new int[15];
    private int cal[]=new int[8];
    private int top=-1;
    private int Q[]=new int[8];
    private int count=0;
    public static void main(String[] args) {

        EightQueue queue = new EightQueue();
        queue.eightQueue(0);
    }

    /**
     * 八皇后
     * @param i
     */
    private  void eightQueue(int i) {
        for(int j=0;j<8;j++){
            if((left[i+j]==0)&&(right[i-j+7]==0)&&(cal[j]==0)){
                left[i+j]=right[i-j+7]=cal[j]=1;
                Q[++top]=j;
                if(top<7)
                eightQueue(i+1);
                else
                {
                    System.out.format("第%个八皇后 ",++count);
                    for(int g=0;g<8;g++){
                        for(int k=0;k<8;k++){
                            if(Q[g]==k){
                                System.out.print(" X ");
                            }
                            else
                                System.out.print(" O ");
                        }
                        System.out.println();
                    }
                }
                left[i+j]=right[i-j+7]=cal[j]=0;
                --top;
            }
        }
    }
}
